The subject invention relates to a method and apparatus for authentication of communications. More particularly, it relates to a method and apparatus whereby a third party may validate that a communication is an authentic communication from a second party sent with the authorization of a first party. Still more particularly, the third party may be a postal service and the second party may be a mailer and the communication may be a postal indicia indicating that a mail piece has been properly franked.
(The following definitions and notations are used in the subject application:
E,D -- are a pair of keys used in a "public key" encryption system.
K -- is a key used in a "secret key" encryption system.
Keys may be specified by use of subscripts or functional notation as necessary. For example, K.sub.i (t) is the key used by the ith party for transaction t.
E[M]; D[M]; K[M] -- represent encryption, using the specified key and the appropriate corresponding encryption technique, of a message M.
E[D[M]]; D[E[M]]; K[K[M]] -- represent decryption, using the specified key and the appropriate corresponding encryption technique; of the encrypted message M.
(M1, E[P]) -- represents an unencrypted message comprising the specified elements. Note elements may have been previously encrypted.
{a'} -- represents a set of numbers or values.
Hard/easy -- as applied to a computation refers to the relation between the cost of the computation and the value of the result. A computation is "hard" if the cost of performing it, using the best available algorithm, is substantially greater than the value of the result. (Those skilled in the art will recognize that this definition of "hard" differs from that used in complexity theory -- where an algorithm is considered hard if the number of steps increases with exponential rapidity with the size of the operand. While the two concepts are related the present definition is preferred in the context of the subject invention, which relates to the protection of economic value rather than theoretical consideration of complexity.)
The "order of a number or variable refers to the number of digits, or bits, needed to express the number or the greatest allowed value of the variable.)
U.S. Pat. No. 4,853,961; to: Pastor; issued Aug. 1, 1989, discloses a method for authenticating documents. In a somewhat simplified embodiment of this method, a first party is provided with a secret key E.sub.s and at least one other key E.sub.i ; a second party is provided with a key D.sub.i and a third party is provided with a key D.sub.s. The key pairs E.sub.s,D.sub.s and E.sub.i,D.sub.i are encryptiondecryption keys for use with a "public key" encryption system such as RSA. RSA is a well known encryption scheme characterized by the use of encryption/decryption key pairs E,D such that if one key, E or D, is used to encrypt a message the other, D or E respectively must be used to decrypt it; and by the fact that it is hard to determine one key from knowledge of the other. Thus, by keeping the decryption key D secret the encryption key E may be publicly distributed so that any person may encrypt a message but only those knowing the decryption key D can decrypt the message.
In the method of the '961 patent the first party first forms a first level message M1 which includes key E.sub.i. The first party then forms a second level message by encrypting the first level Message M1 with key E.sub.s to form a second level message M2 and then sends the second level message M2 to the second party. The first party may further encrypt the second level message M2 with the key E.sub.i before sending it. When the second level message M2 is received by the second party, it is decrypted, if necessary, using key D.sub.i, the second party then encrypts information P using key D.sub.i and combines this encrypted information D.sub.i [P] with the second level message M2 to form a third level message M3. (By "combine" herein is meant some simple operation such as concatenation such that the components of the combined message may be easily recovered by the recipient.) The second party then sends the third level message M3 to the third party.
When the third level message M3 is received by the third party the third party recovers the second level message E.sub.s [M1] and decrypts it with the key D.sub.s to recover the first level message M1. The third party then recovers the key E.sub.i from the first level message and the encrypted information D.sub.i [P] from the third level message and decrypts the encrypted information to recover information P.
Thus, the third party verifies that the information P is an authentic message from the second party sent with the authorization of the first party.
The above described method has two major advantages for applications such as authentication of postal indicia. First, the third party, a postal service, does not need to maintain a large data bank of keys for each mailer, but need only have possession of the key D.sub.s. Secondly, only the key E.sub.s need to be maintained with a high degree of security since indicia cannot be counterfeited using the key D.sub.s and only a single mailer is compromised if a key D.sub.i is compromised. This is advantageous since the postal service will wish to have the ability to authenticate indicia at each of thousands of post offices, while the first party, who may be a provider of postage metering services such as the assignee of the present application, need only have the key E.sub.s available at a single central location. Thus, the invention of the '961 patent provides a highly effective method for its intended purpose. However, it suffers from the disadvantage that to provide a high degree of security keys of a high order are required. It is estimated that it would require only a few seconds of computational time on a modern super computer to break an RSA encryption using a thirty (30) digit key, and it is estimated that adequate security for RSA encryption is achieved only with keys on the order of 150 to 200 digits. Since encrypted messages are of the same order as the key used for encryption, the resulting indicia using the invention of the '961 patent contains a great deal of information and is physically quite large. This is a disadvantage when the message must be incorporated in an indicia on a mail piece, where space is limited.
One encryption scheme which requires a smaller key is the DES technique. This encryption technique was developed by the National Bureau Standards and is commonly used in the financial industry, and requires a key of only 64 binary bits. DES is a "single key" encryption technique where the same key is used both for encryption and decryption. Since it is a single key technique this would mean that in applications such as authenticating postal indicia it would be necessary either for the postal service to maintain a data bank of keys for each mailer, or for the secret key to be available at each post office (since the key for decryption is identical to the key for encryption in DES); greatly decreasing security of the system. Also, recent mathematical discoveries relating to the factorability of large numbers raise some questions as to the security of the RSA technique raising the possibility that keys even larger than 200 digits may be necessary.
Another secret key encryption technique which is significantly more secure than RSA and requires a relatively small key (though somewhat larger than a DES key) is the "eliptical logarithm technique" this technique, while not as commonly used as DES is well known in the cryptographic art and will be described further below. The eliptical logarthm technique is also described in Koblitz, Neal; A Course in Number Theory and Cryptography: Chapter VI, Vol. 114, Graduate Texts in Mathematics: Springer-Verlog (1987)
Thus, it is an object of the subject invention to provide a method and apparatus for the authentication of communications which provides a high degree of security and does not require the party receiving the communication to maintain a large database of encryption keys.
It is a particular object of the subject invention to provide such method an apparatus which are suitable for the authentication of postal indicia.
Other objects and advantages of the subject invention will be apparent to those skilled in the art from consideration of the attached drawings and the detailed description set forth below.